#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2)
    {
        int n = arr1.size();
        map<int, int> ansMap;
        for (int a : arr1)
        {
            ansMap[a]++;
        }
        vector<int> ans;
        for (size_t i = 0; i < arr2.size(); i++)
        {
            int count = ansMap[arr2[i]];
            while (count)
            {
                ans.push_back(arr2[i]);
                count--;
            }
            ansMap.erase(arr2[i]);
        }
        if (!ansMap.empty())
        {
            // sort(ansMap.begin(), ansMap.end());
            for (auto &it : ansMap)
            {
                while (it.second)
                {
                    ans.push_back(it.first);
                    it.second--;
                }
            }
        }
        return ans;
    }

    vector<int> relativeSortArray_2(vector<int> &arr1, vector<int> &arr2)
    {
        unordered_map<int, int> arr2Orders;
        for (int i = 0; i < arr2.size(); i++)
            arr2Orders[arr2[i]] = i;

        sort(arr1.begin(), arr1.end(), [&](const int x, const int y)
             {
            int xPos = arr2Orders.find(x) != arr2Orders.end() ? arr2Orders[x] : arr2.size();
            int yPos = arr2Orders.find(y) != arr2Orders.end() ? arr2Orders[y] : arr2.size();
            return xPos < yPos || (xPos == yPos && x < y); });
        return arr1;
    }

    vector<int> relativeSortArray_3(vector<int> &arr1, vector<int> &arr2)
    {
        unordered_map<int, int> rank;
        for (int i = 0; i < arr2.size(); ++i)
        {
            rank[arr2[i]] = i;
        }
        sort(arr1.begin(), arr1.end(), [&](int x, int y)
             {
            if (rank.count(x)) {
                return rank.count(y) ? rank[x] < rank[y] : true;
            }
            else {
                return rank.count(y) ? false : x < y;
            } });
        // way2 元组排序 c++ >11
        auto mycmp = [&](int x) -> pair<int, int>
        {
            return rank.count(x) ? pair{0, rank[x]} : pair{1, x};
        };
        sort(arr1.begin(), arr1.end(), [&](int x, int y)
             { return mycmp(x) < mycmp(y); });
        // way3
        return arr1;
    }

    /**
     * @brief 计数排序 -1000
     *
     * @param arr1
     * @param arr2
     * @return vector<int>
     */
    vector<int> relativeSortArray_4(vector<int> &arr1, vector<int> &arr2)
    {
        int upper = *max_element(arr1.begin(), arr1.end());
        vector<int> frequency(upper + 1);
        for (int x : arr1)
        {
            ++frequency[x];
        }
        vector<int> ans;
        for (int x : arr2)
        {
            for (int i = 0; i < frequency[x]; ++i)
            {
                ans.push_back(x);
            }
            frequency[x] = 0;
        }
        for (int x = 0; x <= upper; ++x)
        {
            for (int i = 0; i < frequency[x]; ++i)
            {
                ans.push_back(x);
            }
        }
        return ans;
    }
};
int main()
{
    Solution s;
    vector<int> arr1 = {2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}, arr2 = {2, 1, 4, 3, 9, 6};
    vector<int> ans = s.relativeSortArray_3(arr1, arr2);
    for (auto &a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    return 0;
}